package 二叉树;

import java.util.*;

/**
 * @author XZ
 * @create 2021-10-18 14:47
 * https://leetcode-cn.com/problems/binary-tree-postorder-traversal/
 */

/**
 *
 * 重要的是背诵模板，而不是乱写代码。 只要写出了下面这个模板那么不仅能够慢慢想出后序遍历，前中序遍历也能够想出来！！
 while( 栈非空 || p 非空)
 {
 if( p 非空)
 {

 }
 else
 {

 }
 }
 **/
public class _145_二叉树的后序遍历 {
    //1、迭代
    public List<Integer> postorderTraversal1(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        postOrderTraversal(root,list);
        return list;
    }

    private void postOrderTraversal(TreeNode node, List list) {
        if (node==null) return;
        postOrderTraversal(node.left, list);
        postOrderTraversal(node.right,list);
        list.add(node.val);
    }

    //2、遍历
    public List<Integer> postorderTraversal(TreeNode root){
        TreeNode p = root;
        TreeNode r = null;
        List<Integer> list = new ArrayList();
        Stack<TreeNode> deque = new Stack<>();

        while(!deque.isEmpty() || p != null)
        {
            if(p != null)
            {
                deque.push(p);
                p = p.left;
            }
            else
            {
                p = deque.peek();
                if(p.right == null || p.right == r)
                {
                    list.add(p.val);
                    r = p;
                    deque.pop();
                    p = null;
                }
                else
                    p = p.right;
            }
        }
        return list;
    }
}
